//
//  131. 分割回文串.swift
//  手撕代码
//
//  Created by xiaoZuDeMeng on 2024/2/6.
//

import Foundation

// 动态规划+回溯
//https://leetcode.cn/problems/palindrome-partitioning/
//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
//
//回文串 是正着读和反着读都一样的字符串。
//
//
//
//示例 1：
//
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
//示例 2：
//
//输入：s = "a"
//输出：[["a"]]
//
//
//提示：
//
//1 <= s.length <= 16
//s 仅由小写英文字母组成

var ans: [[String]] = []
var dp: [[Bool]] = []

func 分割回文串(_ s: String) -> [[String]] {
    var list = [Character](s)
    var item: [String] = []
    // 使用动态规划的方式统计 位置i到j是否是回文
    dp = [[Bool]].init(repeating: [Bool].init(repeating: true, count: list.count), count: list.count)
    // 初始化边界，默认都是true
    for i in (0..<list.count).reversed() {
        for j in (1 + i)..<list.count {
            dp[i][j] = (list[i] == list[j]) && (dp[i + 1][j - 1])
        }
    }
    backStack(0, &list, &item)
    return ans
}

func backStack(_ start: Int, _ list: inout [Character], _ itemList: inout [String]) {
    if start >= list.count {
        ans.append(itemList)
        return
    }
    for index in start..<list.count {
        let item = Array(list[start...index])
        // 常规判断回文的方式
//        if !bValid(item) {
//            continue
//        }
        
        // 动态规划判断回文的方式
        if !dp[start][index] {
            continue
        }
        // 当前是回文
        itemList.append(String(item))
        backStack(index + 1, &list, &itemList)
        // 回溯
        itemList.removeLast()
    }
}

//常规的回文判断方法
func bValid(_ s:[Character]) -> Bool {
    let len = s.count
    var left = 0,right = len - 1
    while left < right {
        if s[left] != s[right] {
            return false
        }
        left += 1
        right -= 1
    }
    return true
}
